AVL 平衡树

AVL 树是第一种自平衡二叉搜索树，通过旋转维持左右子树高度差（平衡因子）在 、 、 之间。

四种旋转

失衡类型	旋转	场景
LL（左子树的左子树过高）	右旋	插入左子节点左侧
RR（右子树的右子树过高）	左旋	插入右子节点右侧
LR（左子树的右子树过高）	先左旋后右旋	插入左子节点右侧
RL（右子树的左子树过高）	先右旋后左旋	插入右子节点左侧

复杂度

查找、插入、删除均为 ，严格平衡保证不会退化为链表。插入最多 2 次旋转即可恢复平衡，删除可能需要 次旋转。

与红黑树对比

AVL 更严格平衡，查询更快；红黑树放宽平衡条件，插入/删除旋转更少，适合写多场景。